#include <iostream>
#include <vector>
using namespace std;
class Solution {
 public:
  vector<int> path;
  vector<vector<int>> res;
  vector<vector<int>> permute(vector<int>& nums) {
    int len = nums.size();
    vector<bool> used(len, false);
    backtracking(nums, used, len);
    return res;
  }
  void backtracking(vector<int>& nums, vector<bool>& used, int len) {
    if (len == path.size()) {
      res.push_back(path);
      return;
    }
    for (int i = 0; i < len; i++) {
      if (used[i]) {
        continue;
      }
      used[i] = true;
      path.push_back(nums[i]);
      backtracking(nums, used, len);
      used[i] = false;
      path.pop_back();
    }
  }
};